//76最小覆盖子串
/*给定两个字符串 S 和 T，求 S 中包含 T 所有字符的最短连续子字符串的长度，同时要求时间复杂度不得超过 O(n)

示例：输入是两个字符串 S 和 T，输出是一个 S 字符串的子串

- Input: S = "ADOBECODEBANC", T = "ABC"
Output : "BANC"
*/
//
string minWindow(string S, string T)
{
	vector<int> chars(128, 0);	   //表示目前每个字符缺少的数量
	vector<bool> flag(128, false); //表示每个字符是否在 T 中存在
	// 先统计T中的字符情况
	for (int i = 0; i < T.size(); ++i)
	{
		flag[T[i]] = true;
		++chars[T[i]]; //
	}
	// 移动滑动窗口， 不断更改统计数据
	int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;
	for (int r = 0; r < S.size(); ++r)
	{
		if (flag[S[r]])
		{
			if (--chars[S[r]] >= 0)
			{
				++cnt;
			}
			// 若目前滑动窗口已包含T中全部字符，
			// 则尝试将l右移， 在不影响结果的情况下获得最短子字符串
			while (cnt == T.size())
			{
				if (r - l + 1 < min_size)
				{
					min_l = l;
					min_size = r - l + 1;
				}
				if (flag[S[l]] && ++chars[S[l]] > 0)
				{
					--cnt;
				}
				++l;
			}
		}
	}
	return min_size > S.size() ? "" : S.substr(min_l, min_size);
}


//解法2
class Solution
{
public:
	unordered_map<char, int> ori, cnt;

	bool check()
	{
		for (const auto &p : ori)
		{
			if (cnt[p.first] < p.second)
			{
				return false;
			}
		}
		return true;
	}

	string minWindow(string s, string t)
	{
		for (const auto &c : t)
		{
			++ori[c];
		}

		int l = 0, r = -1;
		int len = INT_MAX, ansL = -1, ansR = -1;

		while (r < int(s.size()))
		{
			if (ori.find(s[++r]) != ori.end())
			{
				++cnt[s[r]];
			}
			while (check() && l <= r)
			{
				if (r - l + 1 < len)
				{
					len = r - l + 1;
					ansL = l;
				}
				if (ori.find(s[l]) != ori.end())
				{
					--cnt[s[l]];
				}
				++l;
			}
		}

		return ansL == -1 ? string() : s.substr(ansL, len);
	}
};